package alogrithm.solution;

import java.util.Stack;

import alogrithm.structure.TreeNode;

/*
 * 题目：输入一颗二元查找树，将该树转换为它的镜像，
即在转换后的二元查找树中，左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。
 */
public class P15 {
	public static void mirrorTreeUsingRecursive(TreeNode node)
	{
		if(node==null)return;
		mirrorTreeUsingRecursive(node.getLeftChild());
		mirrorTreeUsingRecursive(node.getRightChild());
		TreeNode temp=node.getLeftChild();
		node.setLeftChild(node.getRightChild());
		node.setRightChild(temp);
	}
	
	public static void mirrorTreeWithoutRecursive(TreeNode node)
	{
		if(node==null)return;
		Stack<TreeNode> s=new Stack<TreeNode>();
		s.push(node);
		while(!s.isEmpty())
		{
			TreeNode tmp=s.pop();
			TreeNode left=tmp.getLeftChild();
			TreeNode right=tmp.getRightChild();
			tmp.setLeftChild(right);
			tmp.setRightChild(left);
			if(right!=null)s.push(right);
			if(left!=null)s.push(left);
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TreeNode n1=new TreeNode(4);
		TreeNode n2=new TreeNode(8);
		TreeNode n3=new TreeNode(12);
		TreeNode n4=new TreeNode(16);
		TreeNode n5=new TreeNode(6,n1,n2);
		TreeNode n6=new TreeNode(14,n3,n4);
		TreeNode n7=new TreeNode(10,n5,n6);
		TreeNode.middleOrderUsingRecursive(n7);
		mirrorTreeUsingRecursive(n7);
		System.out.println();
		TreeNode.middleOrderUsingRecursive(n7);
		mirrorTreeWithoutRecursive(n7);
		System.out.println();
		TreeNode.middleOrderUsingRecursive(n7);

	}

}
